1061E - Politics - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const int inf=0x3f3f3f3f;
struct edge{
int v,w,c,nxt;
}e[N*15];
int n,m,s,t;
int head[N],hd[N],dis[N],vis[N],cnt=1,ans;
void adde(int u,int v,int w,int c)
{e[++cnt].v=v;e[cnt].w=w;e[cnt].c=c;e[cnt].nxt=head[u];head[u]=cnt;}
void add(int u,int v,int w,int c){if(w<0)printf("-1"),exit(0);adde(u,v,w,c);adde(v,u,0,-c);}
bool spfa()
{
memset(dis,0x3f,sizeof(dis));dis[s]=0;
for(int i=1;i<=t;++i)hd[i]=head[i];
queue<int> q;q.push(s);vis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;if(!e[i].w)continue;
if(dis[v]>dis[u]+e[i].c)
{
dis[v]=dis[u]+e[i].c;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
return dis[t]<inf;
}
int dfs(int u,int fl)
{
if(u==t)return fl;int res=0;vis[u]=1;
for(int i=hd[u];i;i=e[i].nxt)
{
hd[u]=i;int v=e[i].v;
if(!e[i].w||dis[v]!=dis[u]+e[i].c||vis[v])continue;
int tmp=dfs(v,min(fl-res,e[i].w));if(!tmp)continue;
res+=tmp;e[i].w-=tmp;e[i^1].w+=tmp;
ans+=tmp*e[i].c;if(res>=fl)break;
}
vis[u]=0;return res;
}
int k,lim[N],siz[N],a,b;
vector<int> G[N],g[N];
void dfs1(int u,int fa)
{
for(int v:g[u])if(v!=fa)
{
dfs1(v,u);
if(lim[v])siz[u]+=lim[v];
else siz[u]+=siz[v];
if(!lim[v])add(u,v,inf,0);
}
if(lim[u])add(s,u,lim[u]-siz[u],0);
}
void dfs2(int u,int fa)
{
for(int v:G[u])if(v!=fa)
{
dfs2(v,u);
if(lim[v])siz[u]+=lim[v];
else siz[u]+=siz[v];
if(!lim[v])add(v,u,inf,0);
}
if(lim[u])add(u,t,lim[u]-siz[u],0);
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
s=n*2+1;t=n*2+2;
for(int i=1,x;i<=n;++i)
scanf("%d",&x),add(i,i+n,1,-x);
for(int i=1,u,v;i<n;++i)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1,u,v;i<n;++i)
{
scanf("%d%d",&u,&v);
G[u+n].push_back(v+n);
G[v+n].push_back(u+n);
}
scanf("%d",&k);
for(int i=1,x;i<=k;++i)
scanf("%d",&x),scanf("%d",&lim[x]);
scanf("%d",&k);
for(int i=1,x;i<=k;++i)
scanf("%d",&x),scanf("%d",&lim[x+n]);
dfs1(a,0);dfs2(b+n,0);
if(lim[a]!=lim[b+n])return printf("-1"),0;
int res=0,x;
while(spfa())while(x=dfs(s,inf))res+=x;
printf("%d",res==lim[a]?-ans:-1);
return 0;
}